/*
 * Spiral Matrix
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example,
Given the following matrix:

[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
You should return [1,2,3,6,9,8,7,4,5]
 */
package com.xinpan.exercise;

import java.util.ArrayList;

public class SpiralMatrix {
    public ArrayList<Integer> spiralOrder(int[][] matrix) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList<Integer> arr = new ArrayList<Integer>();
        
        int h = matrix.length;
        if(h == 0)
            return arr;
        int w = matrix[0].length;
        
        int run = Math.min(h, w);
        
        int i = 0;
        for(; i < run/2; i++)
        {
            for(int j = i; j < w-i; j++)
                arr.add(matrix[i][j]);
            for(int j = i+1; j < h-i; j++)
                arr.add(matrix[j][w-i-1]);
            for(int j = w-i-2; j >= i; j--)
                arr.add(matrix[h-i-1][j]);
            for(int j = h-i-2; j >= i+1; j--)
                arr.add(matrix[j][i]);
        }
        

        if(w <= h && w%2 == 1)
        {
            for(int j = i; j < w-i; j++)
                arr.add(matrix[i][j]);
            for(int j = i+1; j < h-i; j++)
                arr.add(matrix[j][w-i-1]);
        }
        else if(h < w && h%2 == 1)
        {
            for(int j = i; j < w-i; j++)
                arr.add(matrix[i][j]);
            for(int j = i+1; j < h-i; j++)
                arr.add(matrix[j][w-i-1]);
        }
        
        return arr;
    }
}
